A network is one means for exchanging or transferring information (e.g., signals representing data, voice, text, video) among endpoints (e.g., host machines, fax machines or terminals) connected to the network. The network comprises nodes connected, to each other and to the endpoints, by links. Typically, each link is bidirectional, (i.e., information may be conveyed in the forward and reverse directions) and each link is characterized by parameters, such as a bandwidth or capacity in each direction. The nodes advantageously comprise buffers. If a link does not have sufficient capacity to handle information received at a node, a buffer in the node may be used to store the received information until such time as the link has sufficient capacity.
Networks are increasingly being used for the reliable, high-speed transmission of information in digital format between endpoints over wide areas. This increased use is bringing major changes to network services and architecture/infrastructure design. In particular, a wide spectrum of new consumer services, such as video-on-demand and video teleconferencing, are expected to be offered on Broadband Integrated Services Digital Networks (BISDN). The principal technique for transmission in BISDN is called Asynchronous Transfer Mode (ATM). See, S. E. Minzer, "Broadband ISDN and Asynchronous Transfer Mode," IEEE Comm. Mag., pp. 17-24, September 1989.
When information is to be exchanged between two endpoints (an initiating endpoint and a destination endpoint), the initiating endpoint requests that a bidirectional path (i.e., a connection comprising nodes and links) be established in the network between the two endpoints. In an ATM network, the path that is established is a so-called "virtual circuit" (VC), by which it is meant that the endpoint initiating the exchange simply specifies the destination endpoint, and the network delivers the information from the initiating endpoint to the destination endpoint as though they are connected by a direct circuit. The number of "hops" in the path of the VC is equal to the number of links in the path or to one less than the number of nodes in the path.
An important consideration in the operation of a network is whether to admit new VCs onto the network and how to route admitted VCs through the network. In determining whether to admit and how to route requests for VCs from these endpoints, a network admission and routing scheme must reserve resources (e.g., bandwidth on the links comprising the VC). Resource reservation is necessary so as to satisfy any quality-of-service (QOS) guarantees provided by the network, e.g., requirements relating to a maximum information loss rate or maximum delay in receiving information. Resource reservation, in turn, implies the need for admission control to ensure that resources are not reserved on the links and in the nodes in excess of resources that are available.
Generally, the objective of routing and admission control methods is to maximize utilization of the network resources without violating resource constraints and while satisfying any QOS guarantees or requirements. Many factors complicate routing and admission control decisions. First, the decisions may have to be made "on-line," i.e., without knowledge of what effect future routing demands will have on network resources. Although this problem may be solved by so-called "dynamic-rerouting" techniques, these techniques typically adversely affect the quality of service offered to users of the network. Second, the current state of the network (i.e., the network topology and current allocation of network resources) may not be available such as when information about recently allocated resources has not yet been reflected in the network state. In such as case, the routing and admission decision may be based on static or inaccurate state information. Third, the admission and routing decisions must often be made in real time, i.e., within a time interval determined by the VC set up protocol which specifies the amount of time allotted for attempting to establish or set up a VC and which specifies how many attempts to set up a VC are permitted.
Admission control and routing methods typically admit and route requested VCs on selected paths so as to minimize some cost function that reflects the amount of network resources required by the selected path. Although a variety of cost functions can be used, cost functions typically are functions of parameters relating to the current network state, delay through the network.
The manner in which the admission and routing problem for requested virtual circuits is addressed typically is based on factors such as whether the routing is done with incomplete or complete information and on whether the VCs are permanent or switched. In particular, such factors are typically useful in specifying the parameters of the cost function. Routing with incomplete information means simply that the state of the network is not known or, if the state is known, that the state information is dated, e.g., that the available state information does not incorporate information regarding network resources allocated to the most recently routed VCs. Conversely, routing with complete information means that the state information is fully known and that the state information is up-to-date. Large scale networks (e.g., networks comprising on the order of a hundred nodes over a geographic area the size of the United States) cannot expect to have accurate or complete state information available at every node connected to an originating endpoint due to propagation delays in relaying information from node to node. As a consequence, such networks must either make all routing decisions based on complete information at a centralized site (which site has access to all nodes) or the network must make routing decisions locally (i.e., in a distributed manner) based on static or inaccurate state information. Permanent VCs are paths for information transfer between endpoints designed to operate and remain established for long periods of time, perhaps on the order of years. Switched VCs are designed to operate for hours or days.
One admission scheme that has been suggested for permanent VCs and for switched VCs (where the switched VCs are to be established for known durations of time) uses an exponential function of link load to evaluate the cost of routing information on any given path in the network. See, B. Awerbuch et al., "Throughput-Competitive On-Line Routing" 34th Annual Symp. on Foundations of Comp. Sci., Palo Alto, Calif., November 1993. The exponential cost based algorithm of Awerbuch et al., supra, is referred to herein as the "AAP" method.
The AAP method is based on a threshold cost which is determined as a function of an admission threshold and an exponential cost metric for each link in the network. The AAP method, for a requested VC, determines a set of paths on which the requested VC may be routed where the cost of routing on the links in any given path in the set of paths is below the threshold cost. Any request whose cost of routing through the network is above the threshold cost is rejected. The AAP method, however, has several shortcomings. First, the AAP method does not specify which particular path in the set of paths should be used to route the requested VC (i.e., the AAP method performs admission control only and does not select particular paths for or route requested VCs). Moreover, Awerbuch et al. do not indicate how to apply the AAP method in the case of switched VCs which are to be established for unknown durations of time. Other aspects of the AAP method, and in particular the exponential cost function of the AAP method, are examined in the following paragraphs.
Pseudo-code which implements a portion of the AAP exponential-cost based method is shown in Table 1. Each line of the pseudo-code of Table 1 is explained below. Let n denote the number of nodes in the network. The capacity u(e) assigned to each link e in the network represents bandwidth available on that link. Upon receiving a j.sup.th request from an origination endpoint for a VC to a destination endpoint (line 1 of the pseudo-code), the request represented by
(s.sub.j,t.sub.j,r.sub.j,T.sub.j.sup.s,T.sub.j.sup.f), the AAP method attempts to allocate a route or path of capacity r.sub.j from originating node s.sub.j (directly connected to the origination endpoint) to the destination node t.sub.j (connected directly to the destination endpoint) starting at time
T.sub.j.sup.s and ending at time T.sub.j.sup.f. For simplicity, assume that the routing is done at time T.sub.j.sup.s.
The goal of the AAP method is to maximize the throughput of the network, i.e., the amount of information being carried through the network over a time interval. Let
T.sub.j =T.sub.j.sup.f -T.sup.s denote the holding time or duration of the circuit, T denote the maximum possible T.sub.j, and r denote the maximum request bandwidth (rate) r.sub.j. Let the threshold cost for the AAP method be the product of n, r and T.
TABLE 1 (1) ROUTE (s.sub.j,t.sub.j,T.sub.j.sup.s,T.sub.j.sup.f,r.sub.j): (2) .A-inverted..tau.,e.epsilon.E:c.sub.e (.tau.,j).rarw.u(e)(.mu..sup..lambda..sup..sub.e .sup.(.tau.,j) - 1);* (3) if .E-backward. path P in G(V,E) from s.sub.j to r.sub.j s.t. ##EQU1## (5) then route the requested circuit on P, and set: (6) .A-inverted.e.epsilon.P,T.sub.j.sup.s .ltoreq..tau..ltoreq.T.sub.j.sup.f, ##EQU2## (8) else reject the connection
In the AAP method the routing decision is based on the information about the current load (demand) and on the future demand for resources on the links (or edges) of the network, i.e., the routing decision takes into account the demand for requests for VCs that may be routed during the holding time of the j.sup.th VC. The load is measured relative to the edge capacity u(e). Let P.sub.i denote the route used to satisfy the ith request. The load on edge e at time .tau. as seen by the routing method when routing the jth circuit is defined as follows: ##EQU3##
Equation (1) indicates congestion or load on link e at time .tau. due to other requests routed on link e. After computing the load, the next step is to compute the exponential cost as in line 2 of Table 1. In the AAP method the cost of edge e at time .tau., c.sub.e (.tau.,j), when routing the j.sup.th circuit is defined by EQU (2)c.sub.e (.tau.,j)=u(e)(.mu..sup..lambda..sup..sub.e .sup.(.tau.,j) -1),
where .lambda..sub.e is the load on link e (i.e. the percentage of link capacity being utilized) at time .tau. while attempting to route the j.sup.th VC, u(e) is the capacity of link e and .mu. is a parameter. The parameter .mu. is related to: n, the number of nodes in the network, r, the maximum possible value of r.sub.j ; and T, the maximum possible value of T.sub.j. If a set of paths exist for which the cost of routing the requested VC on any path in the set is below the threshold, the request is accepted (lines 3-5). In lines 6-7 of Table 1 the resources required by the routed request are reflected in an updated network state. If the set of paths is the empty set, the request is rejected.
Awerbuch et al. suggests selecting .mu. to be 2nTr/(r.sub.min +1) (where r.sub.min is the smallest bandwidth than any VC will request). The value of .mu. may be on the order of 100,000 for a moderately sized network. Proper selection of high values for the parameter .mu. guarantees routing of a total number of requests for VCs within a factor (on the order of log .mu.) of the number of requests that can be routed by an optimal, off-line routing scheme, i.e., a scheme that has information about all requests in advance.
Although the AAP method guarantees sufficient resources for routing admitted VC requests, the method has a further shortcoming in that it is overly conservative in admitting VCs and thus does not fully utilize network resources. However, simply reducing the value of .mu. causes the AAP method to accept requests in excess of available network resources which is not advantageous since it may mean that the network will not be able to satisfy QOS requirements guaranteed to network users. Additionally, the AAP method requires knowledge of link loads at both current and future times. This knowledge may not be available, may be based on dated information or may require an excessive amount of memory to store.
Thus, there is a need for an improved method for routing and admission control of VCs that will increase utilization of network resources while satisfying QOS requirements which method may also be used in networks of switched VCs where the duration or holding time of the VCs is unknown.